package cn.njupt.countSort;

import cn.njupt.cmpSort.Sort;

import java.util.LinkedList;
import java.util.List;

//桶排序

public class BucketSort extends Sort<Double> {
    @Override
    public void sort() {
        //桶数组
        @SuppressWarnings("unchecked")
        List<Double>[] buckets=new List[10];
        for (int i = 0; i < array.length; i++) {
            int bucketIndex=(int)(array[i]*10);
            List<Double> bucket=buckets[bucketIndex];
            if(bucket==null){
                buckets[bucketIndex]=new LinkedList<>();
                bucket=buckets[bucketIndex];
            }
            bucket.add(array[i]);
        }
        int index=0;
        for(int i=0;i< buckets.length;i++){
            if(buckets[i]==null)continue;
            List<Double> bucket=buckets[i];
            bucket.sort(null);
            for (Double d:bucket){
                array[index++]=d;
            }
        }


    }
}
